'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-01 16:44:55
'''
'''
718. 最长重复子数组
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释: 
长度最长的公共子数组是 [3, 2, 1]。
说明:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
'''
from typing import List
class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        dp = [[0 for _ in B+[0]] for _ in A+[0]]
        re = 0
        for i in range(1, len(A)+1):
            for j in range(1, len(B)+1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                    re = max(re, dp[i][j])
        return re

if __name__ == "__main__":
    solution = Solution()
    A = [1,2,3,2,1]
    B = [3,2,1,4,7]
    print(solution.findLength(A, B))